//Friday, November 13 2009
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;

class TemplateMatching
{
	public:
		string bestMatch(string text, string prefix, string suffix)
		{
			int ret1 = -1;
			int ret2 = -1;
			string ret = "";
			for(int i=0; i<text.length(); i++)
				for(int j=1; j<=text.length(); j++)
			{
				string s = text.substr(i, j);
				int a = score(prefix, s);
				int b = score(s, suffix);
				if((a+b>ret1+ret2) || (a+b==ret1+ret2 && a>ret1) || (a+b==ret1+ret2 && a==ret1 && s<ret))
				{
					ret1 = a;
					ret2 = b;
					ret = s;
					cout << ret1 << ", " << ret2 << endl;
				}
			}
			return ret;
		}
		int score(string s, string s1)
		{
			for(int i=min(s1.length(), s.length()); i>0; i--)
			{
				if(s1.substr(0, i) == s.substr(s.length()-i))
				{
					return i;
				}
			}
			return 0;
		}
};
